﻿/*
 * This file is part of MonoSettlers.
 *
 * Copyright (C) 2010-2011 Christoph Husse
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Authors: 
 *      # Christoph Husse
 * 
 * Also checkout our homepage: http://opensettlers.codeplex.com/
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MonoSettlers
{
    public delegate void DOnAddMovable(MovableManager inManager, Movable inMovable);
    public delegate void DOnRemoveMovable(MovableManager inManager, Movable inMovable);

    /// <summary>
    /// The movable manager is the public interface to pathfinding. Every movable is added here and 
    /// the only (intended) way to change its position is by using <see cref="SetPath"/>. The most
    /// important thing everyone should keep in mind about this path engine: It is deterministic in
    /// the strongest way, meaning it is 100% deterministic within a discrete space-time. This is a very
    /// important foundation for later network synchronization and saving games.
    /// </summary>
    public partial class MovableManager
    {
        internal static readonly double LOG_2_FACTOR = 1.0 / Math.Log(2.0);

        private CooperativeAStar m_AStar; 
        private TopologicalList<Movable> m_Movables;

        /// <summary>
        /// The next cycle time aligned to <see cref="CycleResolution"/>. If <see cref="CurrentCycle"/>
        /// is already aligned, the next aligned cycle is still returned.
        /// </summary>
        public long NextAlignedCycle
        {
            get
            {
                return (CurrentCycle / CycleResolution + 1) * CycleResolution;
            }
        }
        /// <summary>
        /// The current discrete time value. By convention, everwhere else you need a discrete game time,
        /// just return this value of the path engine.
        /// </summary>
        public long CurrentCycle { get { return m_AStar.CurrentCycle; } }
        /// <summary>
        /// Directly holds the discretization granularity. All movable speeds can only be multiples of
        /// this value, but be careful, since performance goes down polynomial (?just a guess) with 
        /// increasing resolution.
        /// </summary>
        public long CycleResolution { get { return m_AStar.CycleResolution; } }
        /// <summary>
        /// Holds the terrain information. Refer to <see cref="TerrainCell"/> for more information.
        /// </summary>
        public TerrainCell[,] Terrain { get { return m_AStar.SearchSpace; } }
        /// <summary>
        /// Width and/or Height in TerrainCells. For performance reasons width and height will always
        /// have the same value and must be a power of two. But don't rely on that outside the path engine.
        /// </summary>
        public Int32 Size { get; private set; }

        /// <summary>
        /// Will be called once for every added movable.
        /// </summary>
        public event DOnAddMovable OnAddMovable;
        /// <summary>
        /// Will be called once for every removed movable.
        /// </summary>
        public event DOnRemoveMovable OnRemoveMovable;

        /// <summary>
        /// SLOW but thread-safe enumeration of all movables.
        /// </summary>
        /// <returns></returns>
        public IEnumerable<Movable> GetMovablesSlow()
        {
            // TODO: ensure thread safety
            return (from e in m_Movables select (Movable)e);
        }

        /// <summary>
        /// Can a movable of the given type walk on given cell?
        /// </summary>
        /// <param name="inCell">Starting at (0,0) the grid position on <see cref="Terrain"/> in TerrainCells.</param>
        /// <param name="inMovableType">An integer movable type.</param>
        /// <returns></returns>
        public bool IsWalkable(Point inCell, int inMovableType)
        {
            return m_AStar.IsWalkable(inCell, inMovableType);
        }

        /// <summary>
        /// Creates a new instance.
        /// </summary>
        /// <param name="inSize">Desired terrain grid width (height) in TerrainCells. Must be a power of two.</param>
        /// <param name="inCurrentCycle">An initial value for <see cref="CurrentCycle"/>.</param>
        /// <param name="inCycleResolution">Desired value for <see cref="CycleResolution"/>.</param>
        public MovableManager(Int32 inSize, Int64 inCurrentCycle, Int64 inCycleResolution) 
        {
            // allocate terrain
            Size = inSize;

            int sizeShift = (int)Math.Floor((Math.Log((double)inSize) * LOG_2_FACTOR) + 0.5);

            if ((int)Math.Pow(2, (double)sizeShift) != inSize)
                throw new ApplicationException("Grid size must be a power of two.");

            TerrainCell[,] searchSpace = new TerrainCell[inSize, inSize];

            for (int x = 0; x < inSize; x++)
            {
                for (int y = 0; y < inSize; y++)
                {
                    searchSpace[x, y] = new TerrainCell() 
                    { 
                        X = x,
                        Y = y,
                    };
                }
            }

            m_AStar = new CooperativeAStar(searchSpace, inCurrentCycle, inCycleResolution);
            m_Movables = new TopologicalList<Movable>(10, Size, Size);  
        }

        /// <summary>
        /// The only place where new paths are acquired. 
        /// </summary>
        private void AcquirePath(Movable inMovable)
        {
            if ((CurrentCycle % CycleResolution) != 0)
                throw new ApplicationException("Path can not be acquired in current cycle.");

            if ((inMovable.Position.XCycles % (int)CyclePoint.CYCLE_MILLIS) != 0)
                throw new ApplicationException("XCycles is not a multiple of node time.");

            if ((inMovable.Position.YCycles % (int)CyclePoint.CYCLE_MILLIS) != 0)
                throw new ApplicationException("YCycles is not a multiple of node time.");

            // acquire new path
            //if (inMovable.HasJob)
            {
                m_AStar.SetDynamicPath(
                    inMovable,
                    inMovable.PathSource,
                    inMovable.PathTarget,
                    0);
            }/*
            else
            {
                m_AStar.SetIdlePath(
                    inMovable,
                    0);
            }*/
        }

        /// <summary>
        /// Adds one to <see cref="CurrentCycle"/> and does the necessary internal work, see remarks.
        /// </summary>
        /// <remarks>
        /// This is one of the most complex and important functions in the whole game. Let's say this it
        /// where it "all" happens. Summarized this is the point where all paths are planned and animated.
        /// The current todos regarding path planning are focused on <see cref="CooperativeAStar"/>, so
        /// a deep understanding of the following first level is not necessary.
        /// TODO: more documentation needed.
        /// </remarks>
        public void AddOneCycle()
        {
            m_AStar.AddOneCycle();

            Boolean canAcquirePath = (CurrentCycle % CycleResolution) == 0;

            foreach (var movable in m_Movables)
            {
                if (movable.ReplanTime >= CurrentCycle)
                {
                    // process path progress
                    var path = movable.Path;
                    var currentNode = movable.CurrentNode.Value;

                    if (currentNode.Direction.HasValue)
                    {
                        // check for grid position change
                        CyclePoint cyclePos = movable.Position;
                        Point prevGrid = movable.Position.ToPoint();
                        Point dirVec = GetDirectionVector(currentNode.Direction.Value);
                        Point currentGrid;

                        cyclePos = cyclePos.AddCycleVector(dirVec);

                        currentGrid = cyclePos.ToPoint();

                        if (movable.Direction != currentNode.Direction)
                        {
                            Direction old = movable.Direction;

                            movable.Direction = currentNode.Direction.Value;

                            movable.RaiseDirectionChange(old);
                        }

                        movable.AddCycleVector(dirVec);

                        Boolean posChangeRaised = false;

                        if (prevGrid != currentGrid)
                        {
                            movable.RaisePositionChange(CyclePoint.FromGrid(prevGrid));

                            posChangeRaised = true;
                        }

                        if ((cyclePos.XCycles == currentGrid.X * (int)CyclePoint.CYCLE_MILLIS) &&
                            (cyclePos.YCycles == currentGrid.Y * (int)CyclePoint.CYCLE_MILLIS))
                        {
                            var nextNode = movable.CurrentNode.Next.Value;
                            CyclePoint prediction = CyclePoint.FromGrid(nextNode.Key.X, nextNode.Key.Y);

                            if (nextNode.Key.Time != CurrentCycle)
                                throw new ApplicationException("Lost synchronization for movable.");

                            if (prediction != movable.Position)
                                throw new ApplicationException("Movable is not where it ought to be.");

                            if (!posChangeRaised)
                                movable.RaisePositionChange(CyclePoint.FromGrid(prevGrid));

                            if (currentGrid == movable.PathTarget)
                            {
                                var handler = movable.ResultHandler;

                                movable.ResultHandler = null;

                                if (handler != null)
                                    handler(true);
                            }

                            movable.CurrentNode = movable.CurrentNode.Next;
                        }
                    }
                    else // if(!currentNode.Direction.HasValue)
                    {
                        PathNodeKey currentKey = movable.CurrentNode.Value.Key;

                        if ((movable.Position.XCycles != currentKey.X * (int)CyclePoint.CYCLE_MILLIS) ||
                                (movable.Position.YCycles != currentKey.Y * (int)CyclePoint.CYCLE_MILLIS))
                            throw new ApplicationException("Movable is not where it ought to be");

                        // wait for block switch
                        var next = movable.CurrentNode.Next;

                        if (next != null)
                        {
                            if (next.Value.Key.Time <= CurrentCycle)
                                movable.CurrentNode = next;
                        }
                    }
                }

                if (movable.ReplanTime <= CurrentCycle)
                {
                    if (canAcquirePath)
                        AcquirePath(movable);
                }
            }
        }

        // self explaining.
        private Point GetDirectionVector(Direction inDirection)
        {
            Point result;

            switch (inDirection)
            {
                case Direction._000: result = new Point(0, -1); break;
                case Direction._045: result = new Point(1, -1); break;
                case Direction._090: result = new Point(1, 0); break;
                case Direction._135: result = new Point(1, 1); break;
                case Direction._180: result = new Point(0, 1); break;
                case Direction._225: result = new Point(-1, 1); break;
                case Direction._270: result = new Point(-1, 0); break;
                case Direction._315: result = new Point(-1, -1); break;
                default:
                    throw new ArgumentException();
            }

            return result;
        }

        /// <summary>
        /// Enumerates movables around the given grid position with increasing distance on average (meaning
        /// is is not strongly sorted by distance, for performance reasons).
        /// </summary>
        /// <param name="inAround"></param>
        /// <param name="inHandler"></param>
        /// <returns></returns>
        public WalkResult EnumMovablesAround(Point inAround, Func<Movable, WalkResult> inHandler)
        {
            return m_Movables.EnumAround(inAround, (movable) => { return inHandler(movable); });
        }

        /// <summary>
        /// It is not checked whether the movable
        /// can be placed/walk where it is. If it can't walk or is to be placed on a non-movable object, it will 
        /// immediately die. Allocated movables have to be released with <see cref="ReleaseMovable"/>.
        /// On success, <see cref="OnAddMovable"/> will be raised.
        /// </summary>
        public void AddMovable(Movable inMovable)
        {
            if (inMovable.Parent != null)
                throw new InvalidOperationException("Movable already has a parent.");

            m_Movables.Add(inMovable);

            inMovable.Parent = this;

            inMovable.Path.AddFirst(new MovablePathNode()
            {
                Movable = inMovable,
                Key = new PathNodeKey(inMovable.Position.XGrid, inMovable.Position.YGrid, NextAlignedCycle),
            });

            if (OnAddMovable != null)
                OnAddMovable(this, inMovable);
        }

        /// <summary>
        /// Removes a movable. You should ALWAYS use the <see cref="OnRemoveMovable"/> event to 
        /// invoke custom code that is ought to be executed on release. The reason is plain and
        /// simple: Anyone else can call this method and this way won't invoke your custom release
        /// code if it is not placed in the event handler.
        /// On success, <see cref="OnRemoveMovable"/> will be raised.
        /// </summary>
        /// <param name="inMovable"></param>
        public void ReleaseMovable(Movable inMovable)
        {
            if (inMovable == null)
                return;

            if (inMovable.Parent != this)
                throw new InvalidOperationException("Movable is not attached to this path engine instance.");

            Movable movable = (Movable)inMovable;

            movable.Stop();
            movable.Path.Clear();

            m_Movables.Remove(movable);

            movable.CurrentNode = null;
            inMovable.Parent = null;

            if (OnRemoveMovable != null)
                OnRemoveMovable(this, movable);
        }

        /// <summary>
        /// See <see cref="SetPath"/>.
        /// </summary>
        public void SetPath(Movable inMovable, Point inTarget)
        {
            SetPath(inMovable, inTarget, null);
        }

        /// <summary>
        /// Sets a path with an optional result handler. It is not guaranteed that a path can be
        /// found, neither that it will be reached. What is guaranteed is that the result handler
        /// is called in any case and only with "true" as parameter if the movable has reached its
        /// destination. Further, a movable with a pending result handler is considered to be non-idle.
        /// If you try to set a path for a movable with a pending result handler ("doing a job"), the 
        /// call will immediately throw an exception!
        /// </summary>
        /// <param name="inMovable">Movable to plan a path for.</param>
        /// <param name="inTarget">Destination for the movable.</param>
        /// <param name="inResultHandler">An optional result handler.</param>
        /// <exception cref="InvalidOperationException">The movable is already doing a job. Call <see cref="Stop"/> first.</exception>
        public void SetPath(Movable inMovable, Point inTarget, Procedure<bool> inResultHandler)
        {
            Movable movable = (Movable)inMovable;

            if (movable.HasJob && !movable.UserControlable)
                throw new InvalidOperationException("The movable is already doing a job.");

            if (movable.PathTarget == inTarget)
            {
                if (inResultHandler != null)
                    inResultHandler(true);

                return;
            }

            movable.ResultHandler = inResultHandler;

            // update path information
            movable.PathTarget = inTarget;
            movable.PathSource = movable.Position.ToPoint();

            movable.Invalidate();
        }

        /// <summary>
        /// See <see cref="SetPath"/>.
        /// </summary>
        public void SetPath(IEnumerable<Movable> inMovables, Point inTarget)
        {
            SetPath(inMovables, inTarget, null);
        }

        /// <summary>
        /// See <see cref="SetPath"/>.
        /// </summary>
        public void SetPath(IEnumerable<Movable> inMovables, Point inTarget, Procedure<bool> inResultHandler)
        {
            foreach (var movable in inMovables)
            {
                SetPath(movable, inTarget, inResultHandler);
            }
        }
    }
}
